"""
无回溯窜匹配算法( KMP算法 )
    一个高效的窜匹配算法(类似字符窜中查找[匹配的子窜)

"""


def gen_pnext(p):
    i, k, m = 0, -1, len(p)
    pnext = [-1]*m
    while i < m-1:
        if k==-1 or p[i]==p[k]:
            i, k = i+1, k+1
            pnext[i] = k
        else:
            k = pnext[k]
    return pnext


# 对 pnext 的优化

# def gen_pnext(p):
#     i, k, m = 0, -1, len(p)
#     pnext = [-1] * m
#     while i < m-1:
#         if k == -1 or p[i] == p[k]:
#             i, k = i + 1, k + 1
#             if p[i] == p[k]:
#                 pnext[i] = pnext[k]
#             else:
#                 pnext[i] = k
#         else:
#             k = pnext[k]
#     return pnext

# print(gen_pnext('abbcabcaabbcaa'))

def matching_KMP(t, p, pnext):
    j, i = 0, 0
    n, m =len(t), len(p)
    while j < n and i < m:
        if i == -1 or t[j] == p[i]:
            j, i = j+1, i+1
        else:
            i = pnext[i]
    if i == m:
        return j-i
    return -1



# t = "ababcabcacbab"
# p = "abcac"

t = "aaacbbcaacb"
p = "aacb"

gp = gen_pnext(p)

print(gp)

t_index = matching_KMP(t, p, gp)

print(t_index)

print(t[t_index:(t_index+len(p))])

